/* 双向线性链表
 *
 *                   LIST
 *             +------+------+
 *    +------  | head | tail | ------+
 *    |        +------+------+       |
 *    |                              |
 *    V           LIST_NODE          V
 * +------+    +------+           +------+
 * | data |    | data |           | data |
 * +------+    +------+           +------+
 * | NULL | <- | prev | <- ... <- | prev |
 * +------+    +------+           +------+
 * | next | -> | next | -> ... -> | NULL |
 * +------+    +------+           +------+
 */
#include <stdlib.h>
#include <stdio.h>
#include "double_link_list.h"

/* 创建节点 */
static LIST_NODE* create_node (int data, LIST_NODE* prev,
	LIST_NODE* next) {
	LIST_NODE* node = malloc (sizeof (LIST_NODE));
	node->data = data;
	node->prev = prev;
	node->next = next;
	return node;
}

/* 销毁节点 */
static LIST_NODE* destroy_node (LIST_NODE* node, LIST_NODE** prev) {
	LIST_NODE* next = node->next;
	if (prev)
		*prev = node->prev;
	free (node);
	return next;
}

/* 创建 */
LIST* list_create (void) {
	LIST* list = malloc (sizeof (LIST));
	list->head = NULL;
	list->tail = NULL;
	return list;
}

/* 销毁 */
void list_destroy (LIST* list) {
	list_clear (list);
	free (list);
}

/* 追加 */
void list_append (LIST* list, int data) {
	list->tail = create_node (data, list->tail, NULL);

	if (list->tail->prev)
		list->tail->prev->next = list->tail;
	else
		list->head = list->tail;
}

/* 前插 */
bool list_insert (LIST* list, size_t pos, int data) {
	LIST_NODE* find = NULL;
	for (find = list->head; find; find = find->next)
		if (! pos--) {
			LIST_NODE* node = create_node (data, find->prev, find);

			if (node->prev)
				node->prev->next = node;
			else
				list->head = node;

			node->next->prev = node;
			return true;
		}

	return false;
}

/* 随机访问 */
int* list_at (LIST* list, size_t pos) {
	LIST_NODE* find = NULL;
	for (find = list->head; find; find = find->next)
		if (! pos--)
			return &find->data;

	return NULL;
}

/* 删除 */
bool list_erase (LIST* list, size_t pos) {
	LIST_NODE* find = NULL;
	for (find = list->head; find; find = find->next)
		if (! pos--) {
			LIST_NODE* prev = NULL;
			LIST_NODE* next = destroy_node (find, &prev);

			if (prev)
				prev->next = next;
			else
				list->head = next;

			if (next)
				next->prev = prev;
			else
				list->tail = prev;

			return true;
		}

	return false;
}

/* 删除所有匹配数据 */
void list_remove (LIST* list, int data) {
	LIST_NODE* find = NULL, *next = NULL;
	for (find = list->head; find; find = next) {
		next = find->next;

		if (find->data == data) {
			LIST_NODE* prev = NULL;
			LIST_NODE* next = destroy_node (find, &prev);

			if (prev)
				prev->next = next;
			else
				list->head = next;

			if (next)
				next->prev = prev;
			else
				list->tail = prev;
		}
	}
}

/* 清空 */
void list_clear (LIST* list) {
	while (list->head)
		list->head = destroy_node (list->head, NULL);
	list->tail = NULL;
}

/* 大小 */
size_t list_size (LIST* list) {
	size_t size = 0;

	LIST_NODE* node = NULL;
	for (node = list->head; node; node = node->next)
		++size;

	return size;
}

/* 判空 */
bool list_empty (LIST* list) {
	return ! list->head && ! list->tail;
}

/*正向遍历*/
void list_forward_traverse(LIST *list)
{
    LIST_NODE *node = list->head;
    for(; node; node=node->next)
    {
        printf("%d ", node->data);
    }
    printf("\n");
}

/*反向遍历*/
void list_reverse_traverse(LIST *list)
{
    LIST_NODE *node = list->tail;
    for(; node; node=node->prev)
    {
        printf("%d ", node->data);
    }
    printf("\n");
}

